home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 1.iso / DEMON / RISCOS2 / TCP_131S.ARC / c / IPROUTE < prev    next >
Text File  |  1994-01-25  |  20KB  |  572 lines
  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  */
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7. #include "global.h"
  8. #include "mbuf.h"
  9. #include "internet.h"
  10. #include "timer.h"
  11. #include "netuser.h"
  12. #include "ip.h"
  13. #include "icmp.h"
  14. #include "iface.h"
  15. #include "trace.h"
  16. #include "misc.h"
  17.  
  18. static int16  hash_ip(int32);
  19. static struct route *rt_lookup(int32);
  20.  
  21. struct route *routes[32][NROUTE];       /* Routing table */
  22. struct route r_default;                 /* Default route entry */
  23.  
  24. int32 ip_addr;
  25. struct ip_stats ip_stats;
  26. struct mbuf *loopq;     /* Queue for loopback packets */
  27.  
  28. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  29.  * coming or going, must pass.
  30.  *
  31.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  32.  * broadcast. The router will kick the packet upstairs regardless of the
  33.  * IP destination address.
  34.  */
  35. int ip_route(struct mbuf *bp, char rxbroadcast)
  36. {
  37.         struct ip ip;                   /* IP header being processed */
  38.         int16 ip_len;                   /* IP header length */
  39.         int16 length;                   /* Length of data portion */
  40.         int32 gateway;                  /* Gateway IP address */
  41.         register struct route *rp;      /* Route table entry */
  42.         struct interface *iface;        /* Output interface, possibly forwarded */
  43.         int16 offset;                   /* Offset into current fragment */
  44.         int16 mf_flag;                  /* Original datagram MF flag */
  45.         int strict = 0;                 /* Strict source routing flag */
  46.         char precedence;                /* Extracted from tos field */
  47.         char delay;
  48.         char throughput;
  49.         char reliability;
  50.         int16 opt_len;          /* Length of current option */
  51.         char *opt;              /* -> beginning of current option */
  52.         char *ptr;              /* -> pointer field in source route fields */
  53.         struct mbuf *tbp;
  54.  
  55.         ip_stats.total++;
  56.         if(len_mbuf(bp) < IPLEN){
  57.                 /* The packet is shorter than a legal IP header */
  58.                 ip_stats.runt++;
  59.                 free_p(bp);
  60.                 return -1;
  61.         }
  62.         /* Sneak a peek at the IP header's IHL field to find its length */
  63.         ip_len = (bp->data[0] & 0xf) << 2;
  64.         if(ip_len < IPLEN){
  65.                 /* The IP header length field is too small */
  66.                 ip_stats.length++;
  67.                 free_p(bp);
  68.                 return -1;
  69.         }
  70.         if(cksum(NULLHEADER,bp,ip_len) != 0){
  71.                 /* Bad IP header checksum; discard */
  72.                 ip_stats.checksum++;
  73.                 free_p(bp);
  74.                 return -1;
  75.         }
  76.         /* Extract IP header */
  77.         ntohip(&ip,&bp);
  78.  
  79.         if(ip.version != IPVERSION){
  80.                 /* We can't handle this version of IP */
  81.                 ip_stats.version++;
  82.                 free_p(bp);
  83.                 return -1;
  84.         }
  85.         /* Trim data segment if necessary. */
  86.         length = ip.length - ip_len;    /* Length of data portion */
  87.         trim_mbuf(&bp,length);  
  88.                                 
  89.         /* Process options, if any. Also compute length of secondary IP
  90.          * header in case fragmentation is needed later
  91.          */
  92.         strict = 0;
  93.         for(opt = ip.options; opt < &ip.options[ip.optlen];opt += opt_len){
  94.  
  95.                 /* Most options have a length field. If this is a EOL or NOOP,
  96.                  * this (garbage) value won't be used
  97.                  */
  98.                 opt_len = uchar(opt[1]);
  99.  
  100.                 switch(opt[0] & OPT_NUMBER){
  101.                 case IP_EOL:
  102.                         goto no_opt;    /* End of options list, we're done */
  103.                 case IP_NOOP:
  104.                         opt_len = 1;
  105.                         break;          /* No operation, skip to next option */
  106.                 case IP_SSROUTE:        /* Strict source route & record route */
  107.                         strict = 1;     /* note fall-thru */
  108.                 case IP_LSROUTE:        /* Loose source route & record route */
  109.                         /* Source routes are ignored unless we're in the
  110.                          * destination field
  111.                          */
  112.                         if(ip.dest != ip_addr)
  113.                                 break;  /* Skip to next option */
  114.                         if(uchar(opt[2]) >= opt_len){
  115.                                 break;  /* Route exhausted; it's for us */
  116.                         }
  117.                         /* Put address for next hop into destination field,
  118.                          * put our address into the route field, and bump
  119.                          * the pointer
  120.                          */
  121.                         ptr = opt + uchar(opt[2]) - 1;
  122.                         ip.dest = get32(ptr);
  123.                         put32(ptr,ip_addr);
  124.                         opt[2] += 4;
  125.                         break;
  126.                 case IP_RROUTE: /* Record route */
  127.                         if(uchar(opt[2]) >= opt_len){
  128.                                 /* Route area exhausted; kick back an error */
  129.                                 union icmp_args icmp_args;
  130.  
  131.                                 icmp_args.pointer = IPLEN + opt - ip.options;
  132.                                 icmp_output(&ip,bp,PARAM_PROB,0,&icmp_args);
  133.                                 free_p(bp);
  134.                                 return -1;
  135.                         }
  136.                         /* Add our address to the route */
  137.                         ptr = opt + uchar(opt[2]) - 1;
  138.                         ptr = put32(ptr,ip_addr);
  139.                         opt[2] += 4;
  140.                         break;
  141.                 }
  142.         }
  143. no_opt:
  144.  
  145.         /* See if it's a broadcast or addressed to us, and kick it upstairs */
  146.         if(ip.dest == ip_addr || rxbroadcast){
  147.                 /* If this is a local loopback packet, place on the loopback
  148.                  * queue for processing in the main loop. This prevents the
  149.                  * infinite stack recursion and other problems that would
  150.                  * otherwise occur when we talk to ourselves, e.g., with ftp
  151.                  */
  152.                 if(ip.source == ip_addr){
  153.                         /* Put IP header back on */
  154.                         if((tbp = htonip(&ip,bp)) == NULLBUF){
  155.                                 free_p(bp);
  156.                                 return -1;
  157.                         }
  158.                         /* Copy loopback packet into new buffer.
  159.                          * This avoids an obscure problem with TCP which
  160.                          * dups its outgoing data before transmission and
  161.                          * then frees it when an ack comes, even though the
  162.                          * receiver might not have actually read it yet
  163.                          */
  164.                         bp = copy_p(tbp,len_mbuf(tbp));
  165.                         free_p(tbp);
  166.                         if(bp == NULLBUF)
  167.                                 return -1;
  168.                         enqueue(&loopq,bp);
  169.                 } else {
  170.                         ip_recv(&ip,bp,rxbroadcast);
  171.                 }
  172.                 return 0;
  173.         }
  174.  
  175.         /* Decrement TTL and discard if zero */
  176.         if(--ip.ttl == 0){
  177.                 /* Send ICMP "Time Exceeded" message */
  178.                 icmp_output(&ip,bp,TIME_EXCEED,0,NULLICMP);
  179.                 free_p(bp);
  180.                 return -1;
  181.         }
  182.         /* Look up target address in routing table */
  183.         if((rp = rt_lookup(ip.dest)) == NULLROUTE){
  184.                 /* No route exists, return unreachable message */
  185.                 icmp_output(&ip,bp,DEST_UNREACH,HOST_UNREACH,NULLICMP);
  186.                 free_p(bp);
  187.                 return -1;
  188.         }
  189.         /* Check for output forwarding and divert if necessary */
  190.         iface = rp->interface;
  191.         if(iface->forw != NULLIF)
  192.                 iface = iface->forw;
  193.  
  194.         /* Find gateway; zero gateway in routing table means "send direct" */
  195.         if(rp->gateway == (int32)0)
  196.                 gateway = ip.dest;
  197.         else
  198.                 gateway = rp->gateway;
  199.  
  200.         if(strict && gateway != ip.dest){
  201.                 /* Strict source routing requires a direct entry */
  202.                 icmp_output(&ip,bp,DEST_UNREACH,ROUTE_FAIL,NULLICMP);
  203.                 free_p(bp);
  204.                 return -1;
  205.         }
  206.         precedence = PREC(ip.tos);
  207.         delay = ip.tos & DELAY;
  208.         throughput = ip.tos & THRUPUT;
  209.         reliability = ip.tos & RELIABILITY;
  210.  
  211.         if(ip.length <= iface->mtu){
  212.                 /* Datagram smaller than interface MTU; put header
  213.                  * back on and send normally
  214.                  */
  215.                 if((tbp = htonip(&ip,bp)) == NULLBUF){
  216.                         free_p(bp);
  217.                         return -1;
  218.                 }
  219.                 return (*iface->send)(tbp,iface,gateway,
  220.                         precedence,delay,throughput,reliability);
  221.         }
  222.         /* Fragmentation needed */
  223.         if(ip.fl_offs & DF){
  224.                 /* Don't Fragment set; return ICMP message and drop */
  225.                 icmp_output(&ip,bp,DEST_UNREACH,FRAG_NEEDED,NULLICMP);
  226.                 free_p(bp);
  227.                 return -1;
  228.         }
  229.         /* Create fragments */
  230.         offset = (ip.fl_offs & F_OFFSET) << 3;
  231.         mf_flag = ip.fl_offs & MF;      /* Save original MF flag */
  232.         while(length != 0){             /* As long as there's data left */
  233.                 int16 fragsize;         /* Size of this fragment's data */
  234.                 struct mbuf *f_data;    /* Data portion of fragment */
  235.  
  236.                 /* After the first fragment, should remove those
  237.                  * options that aren't supposed to be copied on fragmentation
  238.                  */
  239.                 ip.fl_offs = offset >> 3;
  240.                 if(length + ip_len <= iface->mtu){
  241.                         /* Last fragment; send all that remains */
  242.                         fragsize = length;
  243.                         ip.fl_offs |= mf_flag;  /* Pass original MF flag */
  244.                 } else {
  245.                         /* More to come, so send multiple of 8 bytes */
  246.                         fragsize = (iface->mtu - ip_len) & 0xfff8;
  247.                         ip.fl_offs |= MF;
  248.                 }
  249.                 ip.length = fragsize + ip_len;
  250.  
  251.                 /* Move the data fragment into a new, separate mbuf */
  252.                 if((f_data = alloc_mbuf(fragsize)) == NULLBUF){
  253.                         free_p(bp);
  254.                         return -1;
  255.                 }
  256.                 f_data->cnt = pullup(&bp,f_data->data,fragsize);
  257.  
  258.                 /* Put IP header back on */
  259.                 if((tbp = htonip(&ip,f_data)) == NULLBUF){
  260.                         free_p(f_data);
  261.                         free_p(bp);
  262.                         return -1;
  263.                 }
  264.                 /* and ship it out */
  265.                 if((*iface->send)(tbp,iface,gateway,
  266.                         precedence,delay,throughput,reliability) == -1)
  267.                         return -1;
  268.  
  269.                 offset += fragsize;
  270.                 length -= fragsize;
  271.         }
  272.         return 0;
  273. }
  274.  
  275. struct rt_cache rt_cache;
  276.  
  277. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  278. int rt_add(int32 target, unsigned int bits, int32 gateway,
  279.            int metric, struct interface *interface)
  280. {
  281.         struct route *rp,**hp;
  282.         int16 i;
  283.         int32 mask;
  284.  
  285.         if(interface == NULLIF)
  286.                 return -1;
  287.  
  288.         rt_cache.target = 0;    /* Flush cache */
  289.  
  290.         /* Zero bits refers to the default route */
  291.         if(bits == 0){
  292.                 rp = &r_default;
  293.         } else {
  294.                 if(bits > 32)
  295.                         bits = 32;
  296.  
  297.                 /* Mask off don't-care bits */
  298.                 mask = 0xffffffff;
  299.                 for(i=31;i >= bits;i--)
  300.                         mask <<= 1;
  301.  
  302.                 target &= mask;
  303.                 /* Search appropriate chain for existing entry */
  304.                 for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  305.                         if(rp->target == target)
  306.                                 break;
  307.                 }
  308.         }
  309.         if(rp == NULLROUTE){
  310.                 /* The target is not already in the table, so create a new
  311.                  * entry and put it in.
  312.                  */
  313.                 if((rp = (struct route *)malloc(sizeof(struct route))) == NULLROUTE)
  314.                         return -1;      /* No space */
  315.                 /* Insert at head of table */
  316.                 rp->prev = NULLROUTE;
  317.                 hp = &routes[bits-1][hash_ip(target)];
  318.                 rp->next = *hp;
  319.                 if(rp->next != NULLROUTE)
  320.                         rp->next->prev = rp;
  321.                 *hp = rp;
  322.         }
  323.         rp->target = target;
  324.         rp->gateway = gateway;
  325.         rp->metric = metric;
  326.         rp->interface = interface;
  327.  
  328.         return 0;
  329. }
  330.  
  331. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  332.  * if entry was not in table.
  333.  */
  334. int rt_drop(int32 target, unsigned int bits)
  335. {
  336.         register struct route *rp;
  337.         unsigned int i;
  338.         int32 mask;
  339.  
  340.         rt_cache.target = 0;    /* Flush the cache */
  341.  
  342.         if(bits == 0){
  343.                 /* Nail the default entry */
  344.                 r_default.interface = NULLIF;
  345.                 return 0;
  346.         }
  347.         if(bits > 32)
  348.                 bits = 32;
  349.  
  350.         /* Mask off don't-care bits */
  351.         mask = 0xffffffff;
  352.         for(i=31;i >= bits;i--)
  353.                 mask <<= 1;
  354.  
  355.         target &= mask;
  356.  
  357.         /* Search appropriate chain for existing entry */
  358.         for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  359.                 if(rp->target == target)
  360.                         break;
  361.         }
  362.         if(rp == NULLROUTE)
  363.                 return -1;      /* Not in table */
  364.  
  365.         if(rp->next != NULLROUTE)
  366.                 rp->next->prev = rp->prev;
  367.         if(rp->prev != NULLROUTE)
  368.                 rp->prev->next = rp->next;
  369.         else
  370.                 routes[bits-1][hash_ip(target)] = rp->next;
  371.  
  372.         free((char *)rp);
  373.         return 0;
  374. }
  375.  
  376. /* Compute hash function on IP address */
  377. static int16 hash_ip(register int32 addr)
  378. {
  379.         register int16 ret;
  380.  
  381.         ret = hiword(addr);
  382.         ret ^= loword(addr);
  383.         ret %= NROUTE;
  384.         return ret;
  385. }
  386. /* Given an IP address, return the MTU of the local interface used to
  387.  * reach that destination. This is used by TCP to avoid local fragmentation
  388.  */
  389. int16 ip_mtu(int32 addr)
  390. {
  391.         register struct route *rp;
  392.         struct interface *iface;
  393.  
  394.         rp = rt_lookup(addr);
  395.         if(rp == NULLROUTE || rp->interface == NULLIF)
  396.                 return 0;
  397.  
  398.         iface = rp->interface;
  399.         if(iface->forw != NULLIF)
  400.                 return iface->forw->mtu;
  401.         else
  402.                 return iface->mtu;
  403. }
  404. /* Look up target in hash table, matching the entry having the largest number
  405.  * of leading bits in common. Return default route if not found;
  406.  * if default route not set, return NULLROUTE
  407.  */
  408. static struct route *rt_lookup(int32 target)
  409. {
  410.         register struct route *rp;
  411.         int bits;
  412.         int32 tsave;
  413.         int32 mask;
  414.  
  415.         if(target == rt_cache.target)
  416.                 return rt_cache.route;
  417.  
  418.         tsave = target;
  419.  
  420.         mask = ~0;      /* All ones */
  421.         for(bits = 31;bits >= 0; bits--){
  422.                 target &= mask;
  423.                 for(rp = routes[bits][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  424.                         if(rp->target == target){
  425.                                 /* Stash in cache and return */
  426.                                 rt_cache.target = tsave;
  427.                                 rt_cache.route = rp;
  428.                                 return rp;
  429.                         }
  430.                 }
  431.                 mask <<= 1;
  432.         }
  433.         if(r_default.interface != NULLIF){
  434.                 rt_cache.target = tsave;
  435.                 rt_cache.route = &r_default;
  436.                 return &r_default;
  437.         } else
  438.                 return NULLROUTE;
  439. }
  440. /* Convert IP header in host format to network mbuf */
  441. struct mbuf *htonip(struct ip *ip, struct mbuf *data)
  442. {
  443.         int16 hdr_len;
  444.         struct mbuf *bp;
  445.         register char *cp;
  446.         int16 checksum;
  447.  
  448.         hdr_len = IPLEN + ip->optlen;
  449.         if((bp = pushdown(data,hdr_len)) == NULLBUF){
  450.                 free_p(data);
  451.                 return NULLBUF;
  452.         }
  453.         cp = bp->data;
  454.         
  455.         *cp++ = (IPVERSION << 4) | (hdr_len >> 2);
  456.         *cp++ = ip->tos;
  457.         cp = put16(cp,ip->length);
  458.         cp = put16(cp,ip->id);
  459.         cp = put16(cp,ip->fl_offs);
  460.         *cp++ = ip->ttl;
  461.         *cp++ = ip->protocol;
  462.         cp = put16(cp,0);       /* Clear checksum */
  463.         cp = put32(cp,ip->source);
  464.         cp = put32(cp,ip->dest);
  465.         if(ip->optlen != 0)
  466.                 memcpy(cp,ip->options,ip->optlen);
  467.  
  468.         /* Compute checksum and insert into header */
  469.         checksum = cksum(NULLHEADER,bp,hdr_len);
  470.         put16(&bp->data[10],checksum);
  471.  
  472.         return bp;
  473. }
  474. /* Extract an IP header from mbuf */
  475. int ntohip(struct ip *ip, struct mbuf **bpp)
  476. {
  477.         char v_ihl;
  478.         int16 ihl;
  479.  
  480.         v_ihl = pullchar(bpp);
  481.         ip->version = (v_ihl >> 4) & 0xf;
  482.         ip->tos = pullchar(bpp);
  483.         ip->length = pull16(bpp);
  484.         ip->id = pull16(bpp);
  485.         ip->fl_offs = pull16(bpp);
  486.         ip->ttl = pullchar(bpp);
  487.         ip->protocol = pullchar(bpp);
  488.         (void)pull16(bpp);      /* Toss checksum */
  489.         ip->source = pull32(bpp);
  490.         ip->dest = pull32(bpp);
  491.  
  492.         ihl = (v_ihl & 0xf) << 2;
  493.         if(ihl < IPLEN){
  494.                 /* Bogus packet; header is too short */
  495.                 return -1;
  496.         }
  497.         ip->optlen = ihl - IPLEN;
  498.         if(ip->optlen != 0)
  499.                 pullup(bpp,ip->options,ip->optlen);
  500.  
  501.         return ip->optlen + IPLEN;
  502. }
  503. /* Perform end-around-carry adjustment */
  504. int16 eac(register int32 sum)
  505. {
  506.         register int16 csum;
  507.  
  508.         while((csum = sum >> 16) != 0)
  509.                 sum = csum + (sum & 0xffffL);
  510.         return (int16) (sum & 0xffffl); /* Chops to 16 bits */
  511. }
  512. /* Checksum a mbuf chain, with optional pseudo-header */
  513. int16 cksum(struct pseudo_header *ph, struct mbuf *m, int16 len)
  514. {
  515.         register unsigned int cnt, total;
  516.         register int32 sum, csum;
  517.         register char *up;
  518.         int16 csum1;
  519.         int swap = 0;
  520.  
  521.         sum = 0l;
  522.  
  523.         /* Sum pseudo-header, if present */
  524.         if(ph != NULLHEADER){
  525.                 sum = hiword(ph->source);
  526.                 sum += loword(ph->source);
  527.                 sum += hiword(ph->dest);
  528.                 sum += loword(ph->dest);
  529.                 sum += uchar(ph->protocol);
  530.                 sum += ph->length;
  531.         }
  532.         /* Now do each mbuf on the chain */
  533.         for(total = 0; m != NULLBUF && total < len; m = m->next) {
  534.                 cnt = min(m->cnt, len - total);
  535.                 up = (char *)m->data;
  536.                 csum = 0;
  537.  
  538.                 if(((long)up) & 1){
  539.                         /* Handle odd leading byte */
  540.                         if(swap)
  541.                                 csum = uchar(*up++);
  542.                         else
  543.                                 csum = (int16)(uchar(*up++) << 8);
  544.                         cnt--;
  545.                         swap = !swap;
  546.                 }
  547.                 if(cnt > 1){
  548.                         /* Have the primitive checksumming routine do most of
  549.                          * the work. At this point, up is guaranteed to be on
  550.                          * a short boundary
  551.                          */
  552.                         csum1 = lcsum((int16 *)up, cnt >> 1);
  553.                         if(swap)
  554.                                 csum1 = (csum1 << 8) | (csum1 >> 8);
  555.                         csum += csum1;
  556.                 }
  557.                 /* Handle odd trailing byte */
  558.                 if(cnt & 1){
  559.                         if(swap)
  560.                                 csum += uchar(up[--cnt]);
  561.                         else
  562.                                 csum += (int16)(uchar(up[--cnt]) << 8);
  563.                         swap = !swap;
  564.                 }
  565.                 sum += csum;
  566.                 total += m->cnt;
  567.         }
  568.         /* Do final end-around carry, complement and return */
  569.         return ~eac(sum) & 0xffff;
  570. }
  571.  
  572.